# ----------
# User Instructions:
# 
# Create a function compute_value() which returns
# a grid of values. Value is defined as the minimum
# number of moves required to get from a cell to the
# goal. 
#
# If it is impossible to reach the goal from a cell
# you should assign that cell a value of 99.

# ----------

grid = [[0, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 1, 0],
        [0, 0, 1, 1, 1, 0],
        [0, 0, 0, 0, 1, 0]]

init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1]

delta = [[-1, 0 ], # go up
         [ 0, -1], # go left
         [ 1, 0 ], # go down
         [ 0, 1 ]] # go right

delta_name = ['^', '<', 'v', '>']

cost_step = 1 # the cost associated with moving from a cell to an adjacent one.

# ----------------------------------------
# insert code below
# ----------------------------------------
closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))]
 
def compute_value():
    todo = [[len(grid)-1,len(grid[0])-1]]
    compute_value_rec(0,todo)
    return value #make sure your function returns a grid of values as demonstrated in the previous video.


def compute_value_rec(count,todo):
    newTodo = []
    while todo:
        t = todo.pop()
        y = t[0]
        x = t[1]
        if closed[y][x] == 0:
            value[y][x] = count
            closed[y][x] = 1
            for d in delta:
                newY = y+d[0]
                newX = x+d[1]
                if newY >= 0 and newY <= len(grid)-1 and newX >=0 and newX <= len(grid[0])-1 and grid[newY][newX] == 0:
                    newTodo.append([newY,newX])
    if newTodo:
        compute_value_rec(count+1,newTodo)
        

val = compute_value()
for v in val:
    print v

